1. Field of the Invention
The present invention relates to a parallel computer system using a SIMD method constituted by a controller and a plurality of processor elements connected to each other in a lattice configuration.
2. Description of the Related Art
Parallel computer systems are widely used, particularly, in the field of CAD (Computer Aided Design) which necessitates high speed calculation for a LSI (large scale integrated) circuit design. Accordingly, it is desirable to improve techniques to make these processor elements operate more efficiently in order to meet the requirements of high density and high speed LSI.
There are two types of parallel computers based on the connection configuration between the processor elements and the controller. One method is called an MIMD (multiple instruction stream multiple data stream) method which is constituted by a plurality of processor elements and controllers. In this method, each of the processor elements is connected to a corresponding controller, respectively. Accordingly, it is necessary to provide the same number of controllers as there are processors. However, it is difficult to constitute a large scale parallel computer system using this method because a large number of controllers are necessary in accordance with the number of processors, which can be from several tens to several hundreds of processors.
The other method is called an SIMD (single instruction stream multiple data stream) method which is constituted by a plurality of processor elements and one controller. In this method, the controller is connected in parallel to all processor elements. Accordingly, it is possible to constitute a large scale parallel computer which has a large number of processor elements, for example, several tens of thousands of processors. For example, a "Connection Machine" made by Thinking Machines Corporation uses the SIMD method. This system is constituted by several tens of thousands of processor elements.
There are several problems associated with the SIMD type of parallel computer.
A first problem occurs in the synchronization of all the processor elements. In general, two countermeasures are taken for solving this problem. In the first countermeasure, data for obtaining synchronization is exchanged between processor elements through a transmission line. However, it is necessary for all the processor elements to be connected to effectively apply this method. In the second countermeasure a particular signal for obtaining synchronization is output from each processor element. Then, "wired-OR" logic is performed on all of the synchronization signals and the resultant data of the wired-OR is returned to all of the processor elements. However, the number of processor elements is limited in the wired-OR logic approach because a large delay occurs in the wired-OR logic operation.
A second problem occurs in the order of priority use of the bus line. When the number of processor elements reaches from several thousand to several tens of thousands, it is necessary to determined the priority order of use of the bus line.
A third problem occurs in the extraction of essential data from essential processor elements. The essential data is, for example, maximum data or minimum data.
One type of parallel computer system according to the present invention is provided for the solution of the above problems.
The other type of the parallel computer system according to the present invention can control all processor elements so as to effectively and uniformly distribute the processor elements as a load.